package com.school.chapter02.graph_;

//邻接矩阵无向图的实现
public class MatrixNDG {
    int size;           //图的顶点个数
    char[] vertexs;     //图顶点名称
    int[][] matrix;     //图关系矩阵

    public MatrixNDG(char[] vertexs, char[][] edges) {
        size = vertexs.length;
        this.vertexs = vertexs;
        matrix = new int[size][size];   //设定图关系矩阵大小

        for (char[] c :                 //设置矩阵值
                edges) {                //根据顶点名称确定对应矩阵下标
            int p1 = getPosition(c[0]);
            int p2 = getPosition(c[1]);
            matrix[p1][p2] = 1;         //无向图，在两个位置对称存储
            matrix[p2][p1] = 1;
        }
    }

    public void print(){
        for (int[] i :
                matrix) {
            for (int j :
                    i) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }

    private int getPosition(char c){
        for (int i = 0; i < vertexs.length; i++)
            if (vertexs[i] == c)
                return i;
            return -1;
    }

    public static void main(String[] args) {
        char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H','I','J','K'};
        char[][] edges = new char[][]{
                {'A', 'C'},
                {'A', 'D'},
                {'A', 'F'},
                {'B', 'C'},
                {'C', 'D'},
                {'E', 'G'},
                {'D', 'G'},
                {'I','J'},
                {'J','G'},};
        MatrixNDG pG;
        long start=System.nanoTime();
        for(int i=0;i<10000;i++){
            pG = new MatrixNDG(vexs, edges);
//            pG.print();   打印图
        }
        long end=System.nanoTime();
        System.out.println(end-start);
    }
}
